/**
 * @author Thierry Bertin-Mahieux and Jin Yoshikawa
 * @data 04/04/2009
 * Library of operations on polygons
 */

import java.awt.geom.*;
import java.util.*;
import java.awt.*;
import java.io.*;



public class PolyOps {



    // checks if it's the same line or not
    // each line defined by 2 defined by {x1,y1,x2,y2}
    public static boolean same_line(double[] p1, double p2[]){
    	// special case, p1 vertical
    	if (p1[0] == p1[2]){
    		if (p2[0] == p2[2]){ // p2 also vertical
    			if (p1[0] == p2[0]) // same line
    				return true;
    			else return false;
		    }
    		else return false;
	    }
    	if (p2[0] == p2[2]) // only line2 vertical
    		return false;
    	// non vertical case
    	// swaps if necessary
    	p1 = p1.clone();
    	p2 = p2.clone();
    	if (p1[0] > p1[2])
    		swap_points(p1);
    	if (p2[0] > p2[2])
    		swap_points(p2);
    	// compute ax+b
    	double a1 = (p1[3] - p1[1]) * 1. / (p1[2] - p1[0]);
    	double a2 = (p2[3] - p2[1]) * 1. / (p2[2] - p2[0]);
    	if (a1 != a2)
    		return false;
    	double b1 = (p1[1] - a1 * p1[0]);
    	double b2 = (p2[1] - a2 * p2[0]);
    	if (b1 == b2)
    		return true;
    	else
    		return false;
    }


    // return the intersection of two lines, or NULL
    // in particular, returns NULL if same line
    // each line defined by 2 defined by {x1,y1,x2,y2}
    public static double[] intersection_lines(double[] p1, double p2[]){
    	p1 = p1.clone();
    	p2 = p2.clone();
    	// we check the easy case
    	if (same_line(p1,p2))
    		return null;
    	// assume it's not the same line
    	double[] res = {0.,0.};
    	double a1, a2, b1, b2;
    	// swaps if necessary
    	if (p1[0] > p1[2])
    		swap_points(p1);
    	if (p2[0] > p2[2])
    		swap_points(p2);
    	// special case, p1 vertical
    	if (p1[0] == p1[2]){
    		if (p2[0] == p2[2]) // p2 also vertical, can't be same line
    			return null;
    		a2 = (p2[3] - p2[1]) * 1. / (p2[2] - p2[0]);
    		b2 = (p2[1] - a2 * p2[0]);
    		res[0] = p1[0];
    		res[1] = a2 * res[0] + b2;
    		return res;
	    }
    	// special case, p2 vertical
    	if (p2[0] == p2[2]){
    		a1 = (p1[3] - p1[1]) * 1. / (p1[2] - p1[0]);
    		b1 = (p1[1] - a1 * p1[0]);
    		res[0] = p2[0];
    		res[1] = a1 * res[0] + b1;
    		return res;
	    }
    	// normal case, no verticals
    	a1 = (p1[3] - p1[1]) * 1. / (p1[2] - p1[0]);
    	b1 = (p1[1] - a1 * p1[0]);
    	a2 = (p2[3] - p2[1]) * 1. / (p2[2] - p2[0]);
    	b2 = (p2[1] - a2 * p2[0]);
    	// we solve: (a1 - a2) x = b2 - b1
    	res[0] = (b2 - b1) * 1. / (a1 - a2);
    	res[1] = a1 * res[0] + b1;
    	return res;
    }

    
    // return the intersection of two segments, or NULL
    // in particular, returns NULL if same line
    // each line defined by 2 defined by {x1,y1,x2,y2}
    public static double[] intersection_segs(double[] p1, double p2[]){
    	p1 = p1.clone();
    	p2 = p2.clone();
    	if (!Line2D.linesIntersect(p1[0],p1[1],p1[2],p1[3],p2[0],p2[1],p2[2],p2[3]))
    		return null;
    	// swaps if necessary
    	if (p1[0] > p1[2])
    		swap_points(p1);
    	if (p2[0] > p2[2])
    		swap_points(p2);
    	// intersection of the line
    	double[] intersect = intersection_lines(p1,p2);
    	// if null, done
    	if (intersect == null)
    		return null;
    	// else, is the intersect part of both lines?
    	if ( intersect[0] < p1[0] ) return null;
    	if ( intersect[0] > p1[2] ) return null;
    	if ( intersect[0] < p2[0] ) return null;
    	if ( intersect[0] > p2[2] ) return null;
    	// x are ok, y are not in order
    	if ( intersect[1] < Math.min(p1[1],p1[3]) ) return null;
    	if ( intersect[1] > Math.max(p1[1],p1[3]) ) return null;
    	if ( intersect[1] < Math.min(p2[1],p2[3]) ) return null;
    	if ( intersect[1] > Math.max(p2[1],p2[3]) ) return null;
    	// all good!
    	return intersect;
    }


    // returns all the intersection points of 2 polygons
    public static LinkedList<Point2D> intersections_polys(Polygon p1, Polygon p2){
    	LinkedList<double[]> segs1 = poly_segs(p1);
    	LinkedList<double[]> segs2 = poly_segs(p2);
    	LinkedList<Point2D> intersects = new LinkedList<Point2D>();
    	// double iteration
    	for (int k1 = 0; k1 < segs1.size(); k1++)
    		for (int k2 = 0; k2 < segs2.size(); k2++){
    			double[] res;
    			res = intersection_segs(segs1.get(k1),segs2.get(k2));
    			if (res != null)
    				intersects.add( new Point2D.Double(res[0],res[1]) );
    		}
    	return intersects;
    }


    // get all segments from a polygon, as double[]: {x1,y1,x2,y2}
    public static LinkedList<double[]> poly_segs(Polygon p){
    	LinkedList<double[]> res = new LinkedList<double[]>();
    	// links between n points
    	int n = p.npoints;
    	for (int k = 0; k < n - 1; k++){
    		double[] seg = {p.xpoints[k],p.ypoints[k],p.xpoints[k+1],p.ypoints[k+1]};
    		res.addLast(seg);
	    }
    	// link from nth point to first
    	if (n > 0) {
    		double[] seg2 = {p.xpoints[n-1],p.ypoints[n-1],p.xpoints[0],p.ypoints[0]};
    		res.addLast(seg2);
    	}
    	return res;
    }


    // check if points are in clockwise position
    // hack, assumes that if we do a really small step away from the
    // line, we won't cross another vertice. False in theory, works
    // in practice
    public static boolean isClockwise(Polygon p){
    	double delta = 1e-10;
    	double x1 = p.xpoints[0];
    	double y1 = p.ypoints[0];
    	double x2 = p.xpoints[1];
    	double y2 = p.ypoints[1];
    	double x_mid = (x1 + x2) * .5;
    	double y_mid = (y1 + y2) * .5;
    	// normal to the vector
    	double seg[] = {x1,y1,x2,y2};
    	double[] normal = normal_to_seg(seg);
    	// new point
    	double xNew = x_mid + normal[0] * delta;
    	double yNew = y_mid + normal[1] * delta;
    	// check if we contain the new point
    	if (p.contains(xNew,yNew))
    		return true; // it's clockwise
    	return false;
    }

    
    // find the normal to a segment, normalize to 1
    // returns a vector {x,y}
    public static double[] normal_to_seg(double[] seg){
    	// if vec is {x,y}
    	// normal is {y,-x}
    	double x_norm = seg[3]-seg[1];
		double y_norm = -(seg[2]-seg[0]);
		double length = Math.sqrt(x_norm*x_norm + y_norm*y_norm);
		x_norm /= length;
		y_norm /= length;
		double res[] = {x_norm,y_norm};
		return res;
    }


    // create a new polygon identic to p1, but points in reverse order
    public static Polygon reverse_polygon(Polygon p1){
    	int n = p1.npoints;
    	Polygon p2 = new Polygon();
    	for (int k = n - 1; k >= 0; k--)
    		p2.addPoint( p1.xpoints[k], p1.ypoints[k] );
    	return p2;
    }

    // check if clockwise, reverse the points if necessary
    public static Polygon make_clockwise(Polygon p){
    	if ( isClockwise(p) )
    		return p;
    	return reverse_polygon(p);
    }


    // get {x1,y1,x2,y2}
    // change in-place to {x2,y2,x1,y1}
    public static void swap_points(double[] seg){
    	//assert(seg.size() == 4);
    	double x1 = seg[0];
    	double y1 = seg[1];
    	seg[0] = seg[2];
    	seg[1] = seg[3];
    	seg[2] = x1;
    	seg[3] = y1;
    }


    // super important function, expands polygon by ext!
    // assumes no hole
    public static Polygon expand(Polygon p, double ext){
    	p = make_clockwise(p);
    	Polygon res = new Polygon();
    	double[] seg1, seg2, seg1new, seg2new, normal1, normal2, intersect;
    	double[] dir1, dir2;
    	double length, to_interX1, to_interY1;
    	// get segments
    	LinkedList<double[]> segs = poly_segs(p);
    	int num_segs = segs.size();
    	segs.add( segs.get(0) ); // trick to help notation
    	for (int k = 0; k < num_segs; k++){
    		// segments
    		seg1 = segs.get(k);
    		seg2 = segs.get(k+1);
    		if (seg1[2] != seg2[0] || seg1[3] != seg2[1]){
    			System.out.println("prob 3128, polygon inconsistency");
    			System.out.println("seg1[2]="+seg1[2]+",seg2[0]="+seg2[0]);
    			System.out.println("seg1[3]="+seg1[2]+",seg2[1]="+seg2[0]);
    		}
    		// normal
    		normal1 = normal_to_seg(seg1);
    		normal2 = normal_to_seg(seg2);
    		// new segments
    		seg1new = new double[4];
    		seg2new = new double[4];
    		seg1new[0] = seg1[0] - normal1[0] * ext;
    		seg1new[1] = seg1[1] - normal1[1] * ext;
    		seg1new[2] = seg1[2] - normal1[0] * ext;
    		seg1new[3] = seg1[3] - normal1[1] * ext;
    		seg2new[0] = seg2[0] - normal2[0] * ext;
    		seg2new[1] = seg2[1] - normal2[1] * ext;
    		seg2new[2] = seg2[2] - normal2[0] * ext;
    		seg2new[3] = seg2[3] - normal2[1] * ext;

    		intersect = intersection_lines(seg1new,seg2new);
    		if (intersect == null)
    			continue;
    		// *****************************
    		// check if intersection too far
		
    		// vector to intersection, from last point
    		to_interX1 = intersect[0] - seg1new[2];
    		to_interY1 = intersect[1] - seg1new[3];
    		length=Math.sqrt(to_interX1*to_interX1+to_interY1*to_interY1);
    		// we cut before the extension
    		if ( length > 1.5 * ext ){			
    			// compute direction of segments
    			dir1 = new double[2];
    			dir1[0]=-normal1[1]; dir1[1]=normal1[0];
    			dir2 = new double[2];
    			dir2[0]=-normal2[1]; dir2[1]=normal2[0];
    			// compute new points
    			int x1 = (int) (seg1new[2] + 1.5 * ext * dir1[0]);
    			int y1 = (int) (seg1new[3] + 1.5 * ext * dir1[1]);
    			res.addPoint(x1,y1);
    			int x2 = (int) (seg2new[0] - 1.5 * ext * dir2[0]);
    			int y2 = (int) (seg2new[1] - 1.5 * ext * dir2[1]);
    			res.addPoint(x2,y2);

		    }
    		// *****************************

    		// add it to polygon res
    		else
    			res.addPoint( (int) intersect[0], (int) intersect[1] );
	    }
    	return res;
    }

    
    
    // from a segment (starting point + second point)
    // returns a second segment that is the first one rotated by "angle" around the starting point 
    // only returns the new point, same starting point
    public static Point2D seg_plus_angle(Point2D p1, Point2D p2, double angle){
    	// rotation around p1
    	AffineTransform rotate = AffineTransform.getRotateInstance(angle,p1.getX(),p1.getY());
    	// transform
    	Point2D p2_new = new Point2D.Double(0,0);
    	rotate.transform(p2,p2_new);
    	// return 
    	return p2_new;
    }


    // DEBUGGING
    public static void main(String[] args){
       double[] res;
       double[] s1 = {0,0,1,1};
       double[] s2 = {0,1,1,0};
       assert(!PolyOps.same_line(s1,s2));
       res = PolyOps.intersection_lines(s1,s2);
       if(res[0] != 0.5 || res[1] != 0.5) {
    	   System.out.println("prob1 ["+res[0]+","+res[1]+"]");
    	   return;
       }
       res = PolyOps.intersection_segs(s1,s2);
       if(res[0] != 0.5 || res[1] != 0.5) {
    	   System.out.println("prob2 ["+res[0]+","+res[1]+"]");
    	   return;
       }
       s2[0]=0;s2[1]=1;s2[2]=0.25;s2[3]=0.75;
       res = PolyOps.intersection_lines(s1,s2);
       if(res[0] != 0.5 || res[1] != 0.5) {
    	   System.out.println("prob3 ["+res[0]+","+res[1]+"]");
    	   return;
       }
       res = PolyOps.intersection_segs(s1,s2);
       if(res != null) {
    	   System.out.println("prob4 ["+res[0]+","+res[1]+"]");
    	   return;
       }
       // better checks
       LinkedList<Point2D> res2;
       Polygon p1 = new Polygon();
       p1.addPoint(0,0);p1.addPoint(0,2);p1.addPoint(2,2);p1.addPoint(2,0);
       Polygon p2 = new Polygon();
       p2.addPoint(4,0);p2.addPoint(4,2);p2.addPoint(2,2);p2.addPoint(2,0);
       res2 = intersections_polys(p1,p2);
       if (res2.size() != 4) {
    	   System.out.println("prob5, res2.size()=" + res2.size());
    	   for (int k = 0; k < res2.size(); k++)
    		   System.out.println("in res2 = " + res2.get(k));
    	   return;
       }
       Polygon p3 = new Polygon();
       p3.addPoint(1,1);p3.addPoint(3,1);p3.addPoint(3,3);p3.addPoint(1,3);
       res2 = intersections_polys(p1,p3);
       if (res2.size() != 2) {
    	   System.out.println("prob6, res2.size()=" + res2.size());
    	   for (int k = 0; k < res2.size(); k++)
    		   System.out.println("in res2 = " + res2.get(k));
    	   return;
       }
       // clockwise
       boolean res3 = isClockwise(p2);
       assert(!res3);
       assert( isClockwise ( make_clockwise(p2) ) );
       // expand
       Polygon p4 = expand(p1,1);
       LinkedList<double[]> segsp4 = poly_segs(p4);
       assert (segsp4.size() == 4);
       assert (segsp4.get(0)[0] == -1 && segsp4.get(0)[1] == 3);
       assert (segsp4.get(0)[2] == 3 && segsp4.get(0)[3] == 3);
       assert (segsp4.get(2)[0] == 3 && segsp4.get(2)[1] == -1);
       assert (segsp4.get(2)[2] == -1 && segsp4.get(2)[3] == -1);
       //
       //Polygon p5 = new Polygon();
       //p5.addPoint(1,2);p5.addPoint(3,4);p5.addPoint(5,6);
       //System.out.println("x1="+p5.xpoints[0]+",y1="+p5.ypoints[0]);
       // test seg_plus_angle
       Point2D point1 = new Point2D.Double(1,1);
       Point2D point2 = new Point2D.Double(2,1);
       Point2D point3 = seg_plus_angle(point1,point2,Math.PI/2);
       assert (point3.getX() == 1.);
       assert (point3.getY() == 2.);
       System.out.println("PolyOps, sanity checks passed");
    }


}
